from typing import List


def heapSort(nums: List, n: int):
    if len(nums) < 2:
        return
    nums.insert(0, 0)
    for i in range(n//2, 0, -1):
        sift(nums, i, n)
    for i in range(n, 1, -1):
        nums[1], nums[i] = nums[i], nums[1]
        sift(nums, 1, i-1)
    return nums[1:]


def sift(nums: List, low: int, high: int):
    i = low
    j = 2 * i
    temp = nums[i]
    while j <= high:
        if j < high and nums[j] < nums[j+1]:
            j += 1
        if temp < nums[j]:
            nums[i] = nums[j]
            i = j
            j = 2 * i
        else:
            break
    nums[i] = temp


if __name__ == '__main__':
    t = [3, 1, 5, -6, 7, 12, 2, 9, 10]
    n = len(t)
    print(heapSort(t, n))
